package org.raymond.iworks.study.basic.structure.stack;

import java.util.Objects;
import java.util.Stack;

/**
 * @author raymond
 * @version V1.0
 * 中缀表达式转后缀表达式:
 * 1) 初始化两个栈:符号栈s1和中间结果栈s2
 * 2) 从左至右扫描中缀表达式
 * 3) 遇到操作数时,压入s2
 * 4) 遇到符号时,比较其与s1栈顶运算符的优先级:
 * 4.0) 括号不与运算符比较优先级
 * 4.1) 如果s1为空,或栈顶符号为左括号"(",则此符号直接入栈
 * 4.2) 否则,若优先级比栈顶运算符高,则此符号直接入栈
 * 4.3) 否则,将s1栈顶的运算符弹出,压入s2,再次转到4.1与s1中新的栈顶运算符相比较
 * 5) 遇到括号时:
 * 5.1) 如果是左括号"(",则直接压入s1
 * 5.2) 如果是右括号")",则依次弹出s1,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃
 * 6) 重复步骤2至5,直到表达式的最右边
 * 7) 将s1中剩余的运算符依次弹出并压入s2
 * 8) 依次弹出s2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式
 */
public class PolandNotation {
    public static void main(String[] args) {
        String infix = post2InFix();
        test1(infix);
    }

    public static String post2InFix(){
        String expr = "4 * 5 - 8 + 60 + 8 / 2";
        expr = "3 * 2 - 6 * 9 + 4 / 2 - 10";
        //expr = "1 * 2 * 3 + 5 * 9 / 3 - 25";
        //expr = "( 30 + 4 ) * 5 - 6";
        expr = "1 + ( ( 2 + 3 ) * 4 ) - 5";
        return infix2Postfix(expr);
    }

    public static void testPostFix(){
        // 为了方便,逆波兰表达式中的数字和符号都用空格隔开
        String expr = "30 4 + 5 * 6 -";
        expr = "4 5 * 8 - 60 + 8 2 / +";
        expr = "1 2 3 + 4 * + 5 -";
        //expr = "1 2 * 3 * 5 9 * 3 / + 25 -";
        test1(expr);
    }

    public static void test1(String expr) {
        Stack<Integer> numStack = new Stack<>();
        // 扫描表达式
        String[] datas = expr.split(" ");
        for (int i = 0; i < datas.length; i++) {
            String data = datas[i];
            char c = data.charAt(0);
            if(data.matches("\\d+")){
                numStack.push(Integer.parseInt(data));
            }else{
                int res = cal(numStack, c);
                numStack.push(res);
            }
        }
        System.out.printf("计算结果:%d\n", numStack.pop());
    }

    public static String infix2Postfix(String infix){
        Stack<Character> operStack = new Stack<>(); //s1
        Stack<String> middleStack = new Stack<>(); //s2
        String[] datas = infix.split(" ");
        for (int i = 0; i < datas.length; i++) {
            String data = datas[i];
            Character c = data.charAt(0);
            if(data.matches("\\d+")) {
                middleStack.push(data);
            }else if(operStack.size()==0){
                operStack.push(c);
            }else{
                Character topOper = operStack.peek();
                if(topOper.equals('(') || c.equals('(')){
                    operStack.push(c);
                // 如果扫描到的是右括号
                } else if(c.equals(')')){
                    // 从s1弹出符号
                    Character tmp = operStack.pop();
                    // 将弹出的符号压入s2,直到左括号时,丢弃左右括号
                    while(!tmp.equals('(')){
                        middleStack.push(String.valueOf(tmp));
                        // 依次从s1弹出符号
                        tmp = operStack.pop();
                    }
                } else {
                    int p1 = priority(c);
                    int p2 = priority(topOper);
                    if (p1 > p2) {
                        operStack.push(c);
                    }else{
                        middleStack.push(String.valueOf(operStack.pop()));
                        // 当前字符串重新进行处理 4.3
                        i--;
                    }
                }
            }
        }
        // 将s1中剩余符号弹出并压入s2
        operStack.stream().map(Objects::toString).forEach(middleStack::push);
        //String result = middleStack.stream().collect(Collectors.joining(" "));
        String result = String.join(" ", middleStack);
        System.out.printf("中缀转后缀结果: %s\n", result);
        return result;
    }

    public static int cal(Stack<Integer> numStack, int oper){
        int num1=numStack.pop();
        int num2=numStack.pop();
        return ArrayStack2.cal(num1,num2,oper);
    }

    public static int priority(int oper){
        if(oper=='*' || oper=='/'){
            return 1;
        }else if(oper == '+' || oper == '-'){
            return 0;
        }else{
            return -1; //假定目前只有+-*/
        }
    }
}
